package leetcode_字符串._06字符的统计;

import java.util.*;

/**
 * 根据字符出现频率排序
 * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列
 * 算法 :
 *   直接用 map 保存字母出现的次数
 *   桶排序
 */
public class _451 {
    public static void main(String[] args) {
        ArrayList<Character> list = new ArrayList<>();
        list.add('a');
        list.add('a');
        System.out.println(list);
    }

    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 创建桶 , 这里的索引表示字符出现的次数
        List<Character>[] bucket = new List[s.length() + 1];
        for (char c : map.keySet()) {
            int value = map.get(c);
            if (null == bucket[value]) {
                bucket[value] = new ArrayList<Character>();
            }
            bucket[value].add(c);
        }
        StringBuilder ans = new StringBuilder();
        // 从后往前遍历桶 , 这样出现次数多的字符先被添加到 ans 字符串中
        for (int i = bucket.length - 1; i > 0; --i) {
            if (null != bucket[i]) {
                for (int j = 0; j < bucket[i].size(); j++) {
                    for (int k = 0; k < i; k++) {
                        ans.append(bucket[i].get(j));
                    }
                }
            }
        }
        return ans.toString();
    }

    public String method_1(Map<Character, Integer> map) {
        StringBuilder ans = new StringBuilder();
        map.entrySet().stream()
                .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
                .forEach(entry -> {
                    for (int i = 0; i < entry.getValue(); i++) {
                        ans.append(entry.getKey());
                    }
                });
        return ans.toString();
    }

}
